{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Visible People in a Queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canSeePersonsCount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #队列中可以看到的人数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有&nbsp;<code>n</code>&nbsp;个人排成一个队列，<strong>从左到右</strong>&nbsp;编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;。给你以一个整数数组&nbsp;<code>heights</code>&nbsp;，每个整数 <strong>互不相同</strong>，<code>heights[i]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;个人的高度。</p>\n",
    "\n",
    "<p>一个人能 <strong>看到</strong> 他右边另一个人的条件是这两人之间的所有人都比他们两人 <strong>矮</strong>&nbsp;。更正式的，第&nbsp;<code>i</code>&nbsp;个人能看到第&nbsp;<code>j</code>&nbsp;个人的条件是&nbsp;<code>i &lt; j</code>&nbsp;且&nbsp;<code>min(heights[i], heights[j]) &gt; max(heights[i+1], heights[i+2], ..., heights[j-1])</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回一个长度为 <code>n</code>&nbsp;的数组<em>&nbsp;</em><code>answer</code><em>&nbsp;</em>，其中<em>&nbsp;</em><code>answer[i]</code><em>&nbsp;</em>是第&nbsp;<code>i</code>&nbsp;个人在他右侧队列中能&nbsp;<strong>看到</strong>&nbsp;的&nbsp;<strong>人数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/29/queue-plane.jpg\" style=\"width: 600px; height: 247px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>heights = [10,6,8,5,11,9]\n",
    "<b>输出：</b>[3,1,2,1,1,0]\n",
    "<strong>解释：</strong>\n",
    "第 0 个人能看到编号为 1 ，2 和 4 的人。\n",
    "第 1 个人能看到编号为 2 的人。\n",
    "第 2 个人能看到编号为 3 和 4 的人。\n",
    "第 3 个人能看到编号为 4 的人。\n",
    "第 4 个人能看到编号为 5 的人。\n",
    "第 5 个人谁也看不到因为他右边没人。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>heights = [5,1,2,3,10]\n",
    "<b>输出：</b>[4,1,1,1,0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == heights.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= heights[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>heights</code>&nbsp;中所有数 <strong>互不相同</strong>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-visible-people-in-a-queue](https://leetcode.cn/problems/number-of-visible-people-in-a-queue/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-visible-people-in-a-queue](https://leetcode.cn/problems/number-of-visible-people-in-a-queue/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,6,8,5,11,9]', '[5,1,2,3,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 单调栈\n",
    "def canSeePersonsCount(heights: List[int]) -> List[int]:\n",
    "    res = [0] * len(heights)\n",
    "    stack = []\n",
    "    for i in range(len(heights) - 1, -1, -1):\n",
    "        while stack and stack[-1] < heights[i]:  # 必须要严格小于才不会被挡住\n",
    "            res[i] += 1\n",
    "            stack.pop()\n",
    "\n",
    "        if stack:\n",
    "            res[i] += 1\n",
    "\n",
    "        while stack and stack[-1] == heights[i]:  # 相等的全部出栈\n",
    "            stack.pop()\n",
    "\n",
    "        stack.append(heights[i])\n",
    "\n",
    "    return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for r, row in enumerate(matrix):\n",
    "            cur = canSeePersonsCount(row)\n",
    "            for c, num in enumerate(cur):\n",
    "                res[r][c] += num\n",
    "\n",
    "        for c, col in enumerate(zip(*matrix)):\n",
    "            cur = canSeePersonsCount(list(col))\n",
    "            for r, num in enumerate(cur):\n",
    "                res[r][c] += num\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def canSeePersonsCount(heights: List[int]) -> List[int]:\n",
    "    res = [0] * len(heights)\n",
    "    stack = []\n",
    "    for i in range(len(heights) - 1, -1, -1):\n",
    "        while stack and stack[-1] < heights[i]:  # 必须要严格小于才不会被挡住\n",
    "            res[i] += 1\n",
    "            stack.pop()\n",
    "        if stack:\n",
    "            res[i] += 1\n",
    "        while stack and stack[-1] == heights[i]:  # 相等的全部出栈\n",
    "            stack.pop()\n",
    "        stack.append(heights[i])\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for r, row in enumerate(matrix):\n",
    "            cur = canSeePersonsCount(row)\n",
    "            for c, num in enumerate(cur):\n",
    "                res[r][c] += num\n",
    "\n",
    "        for c, col in enumerate(zip(*matrix)):\n",
    "            cur = canSeePersonsCount(list(col))\n",
    "            for r, num in enumerate(cur):\n",
    "                res[r][c] += num\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def canSeePersonsCount(x: int,heights: List[int]) -> List[int]:\n",
    "    res = [0 for _ in range(x)]\n",
    "    stack = []\n",
    "    for i in range(x - 1, -1, -1):\n",
    "        while stack and stack[-1] < heights[i]:  # 必须要严格小于才不会被挡住\n",
    "            res[i] += 1\n",
    "            stack.pop()\n",
    "        if stack:\n",
    "            res[i] += 1\n",
    "        while stack and stack[-1] == heights[i]:  # 相等的全部出栈\n",
    "            stack.pop()\n",
    "        stack.append(heights[i])\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def seePeople(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for r, row in enumerate(matrix):\n",
    "            cur = canSeePersonsCount(n, row)\n",
    "            for c, num in enumerate(cur):\n",
    "                res[r][c] += num\n",
    "\n",
    "        for c, col in enumerate(zip(*matrix)):\n",
    "            cur = canSeePersonsCount(m, list(col))\n",
    "            for r, num in enumerate(cur):\n",
    "                res[r][c] += num\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        # a shorter one can be seen by its previous higher one\n",
    "        # it can also see its next higher one\n",
    "        \n",
    "        res = [0]*len(heights)\n",
    "        stack = []\n",
    "        heights.append(float('inf'))\n",
    "        for i, h in enumerate(heights):\n",
    "            while stack and heights[stack[-1]] <= h:\n",
    "                # this is to add to the one need to be popped off from the stack, since it can see its right higher one\n",
    "                if i != len(heights) -1:\n",
    "                    res[stack[-1]] += 1\n",
    "                stack.pop()\n",
    "                if stack:\n",
    "                    res[stack[-1]] += 1\n",
    "            stack.append(i)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        stk,n=[],len(heights)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x=heights[i];heights[i]=len(stk)\n",
    "            while(len(stk) and stk[-1]<=x):del stk[-1]\n",
    "            heights[i]-=len(stk)-(len(stk)>0)\n",
    "            stk.append(x)\n",
    "        return heights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        l = len(heights)\n",
    "        res = [0] * l\n",
    "\n",
    "        stack = [heights[-1]]\n",
    "        if l >= 2:\n",
    "            res[-2] = 1\n",
    "            stack = [heights[-1], heights[-2]]\n",
    "\n",
    "        for i in range(l - 3, -1, -1):\n",
    "            s = 1\n",
    "\n",
    "            while (len(stack) >= 2) and (heights[i] > stack[-1]) and (stack[-1] < stack[-2]):\n",
    "                stack.pop()\n",
    "                s += 1\n",
    "\n",
    "            stack.append(heights[i])\n",
    "\n",
    "            res[i] = s\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        l = len(heights)\n",
    "        res = [0] * l\n",
    "\n",
    "        stack = [heights[-1]]\n",
    "        if l >= 2:\n",
    "            res[-2] = 1\n",
    "            stack = [heights[-1], heights[-2]]\n",
    "\n",
    "        for i in range(l - 3, -1, -1):\n",
    "            s = 1\n",
    "\n",
    "            while (len(stack) >= 2) and (heights[i] > stack[-1]) and (stack[-1] < stack[-2]):\n",
    "                stack.pop()\n",
    "                s += 1\n",
    "\n",
    "            stack.append(heights[i])\n",
    "\n",
    "            res[i] = s\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        ans = [0] * len(heights)\n",
    "        for i,x in enumerate(heights):\n",
    "            while st and heights[st[-1]] < x:\n",
    "                ans[st.pop()] += 1\n",
    "            if st: ans[st[-1]] += 1\n",
    "            st.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and heights[stk[-1]] < heights[i]:\n",
    "                ans[i] += 1\n",
    "                stk.pop()\n",
    "            if stk: ans[i] += 1\n",
    "            stk.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        stk = list()\n",
    "        stk.append(inf)\n",
    "        ans = [0]*n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stk[len(stk)-1]<heights[i]:\n",
    "                stk = stk[:len(stk)-1]\n",
    "                ans[i]+=1\n",
    "            if len(stk)>1:ans[i]+=1\n",
    "            stk.append(heights[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        # 单调栈\n",
    "        queue = deque([])\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = heights[i]\n",
    "            if queue:\n",
    "                j = bisect_left(queue, x)\n",
    "                if j == len(queue):\n",
    "                    j -= 1\n",
    "                ans[i] = j + 1\n",
    "            while queue and x > queue[0]:\n",
    "                queue.popleft()\n",
    "            queue.appendleft(x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        stk = [inf]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and heights[i] > stk[-1]:\n",
    "                stk.pop()\n",
    "                ans[i] += 1\n",
    "            if len(stk) > 1:\n",
    "                ans[i] += 1\n",
    "            stk.append(heights[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        l = len(heights)\n",
    "        res = [0] * l\n",
    "\n",
    "        stack = [heights[-1]]\n",
    "        if l >= 2:\n",
    "            res[-2] = 1\n",
    "            stack = [heights[-1], heights[-2]]\n",
    "\n",
    "        for i in range(l - 3, -1, -1):\n",
    "            s = 1\n",
    "\n",
    "            while (len(stack) >= 2) and (heights[i] > stack[-1]) and (stack[-1] < stack[-2]):\n",
    "                _ = stack.pop()\n",
    "                s += 1\n",
    "\n",
    "            stack.append(heights[i])\n",
    "\n",
    "            res[i] = s\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        l = len(heights)\n",
    "        res = [0] * l\n",
    "\n",
    "        stack = [heights[-1]]\n",
    "        if l >= 2:\n",
    "            res[-2] = 1\n",
    "            stack = [heights[-1], heights[-2]]\n",
    "\n",
    "        for i in range(l - 3, -1, -1):\n",
    "            s = 1\n",
    "\n",
    "            while (len(stack) >= 2) and (heights[i] > stack[-1]) and (stack[-1] < stack[-2]):\n",
    "                stack.pop()\n",
    "                s += 1\n",
    "\n",
    "            stack.append(heights[i])\n",
    "\n",
    "            res[i] = s\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 要学会转化问题\n",
    "# 如果一个人可以看到其右边的人，就代表着左边的人不能将其挡住\n",
    "# 需要维护一个单调递增的序列\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        stk = [inf]\n",
    "        ans = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cnt = 0\n",
    "            while stk and heights[i] >= stk[-1]:\n",
    "                stk.pop()\n",
    "                cnt += 1\n",
    "            if len(stk) > 1: cnt += 1  \n",
    "            ans[i] = cnt\n",
    "            stk.append(heights[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        s = [0]\n",
    "        ans = [0] * n \n",
    "        for i in range(1, n):\n",
    "            if heights[i] < heights[s[-1]]:\n",
    "                ans[s[-1]] += 1                \n",
    "            else:\n",
    "                while s and heights[i] >= heights[s[-1]]:\n",
    "                    ans[s.pop()] += 1\n",
    "                if s:\n",
    "                    ans[s[-1]] += 1\n",
    "            s.append(i)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        stack = [heights[-1]]\n",
    "        ans = [0] * len(heights)\n",
    "        for i in range(len(heights)-2, -1, -1):\n",
    "            L, R = 0, len(stack)-1\n",
    "            while L <= R:\n",
    "                mid = (L + R) // 2\n",
    "                if stack[mid] > heights[i]:\n",
    "                    L = mid + 1\n",
    "                else:\n",
    "                    R = mid - 1\n",
    "            ans[i] = len(stack) - max(1, L) + 1\n",
    "\n",
    "            while stack and stack[-1] < heights[i]:\n",
    "                stack.pop()\n",
    "            stack.append(heights[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        s = []\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            while s and heights[s[-1]] < heights[i]:\n",
    "                j = s.pop()\n",
    "                if s: ans[s[-1]] += 1\n",
    "                ans[j] += 1\n",
    "            s.append(i)\n",
    "        while s:\n",
    "            s.pop()\n",
    "            if s: ans[s[-1]] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(heights)\n",
    "        r = [0] * n\n",
    "        st = []\n",
    "\n",
    "        for i in range(n):\n",
    "            while st and heights[st[-1]] <= heights[i]:\n",
    "                r[st.pop()] += 1\n",
    "            if st: r[st[-1]] += 1\n",
    "            st.append(i)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        stack = []\n",
    "        res = [0] * n\n",
    "\n",
    "        for i in range(n) :\n",
    "            while stack and heights[i] > heights[stack[-1]] :\n",
    "                idx = stack[-1]\n",
    "                stack.pop()\n",
    "                res[idx] += 1\n",
    "                \n",
    "            if stack :\n",
    "                res[stack[-1]] += 1\n",
    "            stack.append(i)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        # 初始化结果数组和单调递减栈\n",
    "        n = len(heights)\n",
    "        res = [0] * n\n",
    "        stack = []\n",
    "        \n",
    "        for i in range(n):\n",
    "            # 由于栈是单调递减的，如果当前的高度大于栈顶的高度，\n",
    "            # 那么就可以看到栈中所有更小的高度。\n",
    "            while stack and heights[i] > heights[stack[-1]]:\n",
    "                last = stack.pop()\n",
    "                res[last] += 1\n",
    "            \n",
    "            # 如果栈不为空，那么栈顶的人能看到当前的人。\n",
    "            if stack:\n",
    "                res[stack[-1]] += 1\n",
    "            \n",
    "            # 把当前的人加入到栈中。\n",
    "            stack.append(i)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        stack = [inf]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            h = heights[i]\n",
    "            while stack[-1] < h:\n",
    "                stack.pop()\n",
    "                ans[i] += 1\n",
    "            if len(stack) > 1:\n",
    "                ans[i] += 1\n",
    "            stack.append(h)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        l = len(heights)\n",
    "\n",
    "        res = [0] * l\n",
    "\n",
    "        stack = [heights[-1]]\n",
    "\n",
    "        if l >= 2:\n",
    "            res[-2] = 1\n",
    "            stack = [heights[-1], heights[-2]]\n",
    "\n",
    "        for i in range(l - 3, -1, -1):\n",
    "            s = 1  # 表示至少能看到右侧一人\n",
    "\n",
    "            while (len(stack) >= 2) and (heights[i] > stack[-1]) and (stack[-1] < stack[-2]):\n",
    "                stack.pop()\n",
    "                s += 1\n",
    "\n",
    "            stack.append(heights[i])\n",
    "\n",
    "            res[i] = s\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0]*n\n",
    "        s = []#存储递减序列\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while s:\n",
    "                ans[i] += 1 #i与s[-1]相邻，肯定能看到\n",
    "                if heights[i]>heights[s[-1]]: #i<s[-1] 表示i之前的都无法看到了，需pop\n",
    "                    s.pop()\n",
    "                else:\n",
    "                    break \n",
    "            s.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        stack = [heights[-1]]\n",
    "        ans = [0] * len(heights)\n",
    "        for i in range(len(heights)-2, -1, -1):\n",
    "            L, R = 0, len(stack)-1\n",
    "            while L <= R:\n",
    "                mid = (L + R) // 2\n",
    "                if stack[mid] > heights[i]:\n",
    "                    L = mid + 1\n",
    "                else:\n",
    "                    R = mid - 1\n",
    "            ans[i] = len(stack) - max(1, L) + 1\n",
    "\n",
    "            while stack and stack[-1] < heights[i]:\n",
    "                stack.pop()\n",
    "            stack.append(heights[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        stack = [heights[-1]]\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            cnt = 0\n",
    "            while stack and stack[-1] <= heights[i]:\n",
    "                stack.pop()\n",
    "                cnt += 1\n",
    "            if stack:\n",
    "                cnt += 1\n",
    "            ans[i] = cnt\n",
    "            stack.append(heights[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        st = deque()\n",
    "        ans = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cur = 0 if not st else 1\n",
    "            if st:\n",
    "                idx = bisect.bisect_right(st, heights[i])\n",
    "                if idx < len(st) and st[idx] > heights[i]:\n",
    "                    idx += 1\n",
    "                cur = max(cur, idx)\n",
    "            ans[i] = cur\n",
    "            #print(i, cur, st)\n",
    "            while st and heights[i] >= st[0]:\n",
    "                st.popleft()\n",
    "            st.appendleft(heights[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n=len(heights)\n",
    "        s=list()\n",
    "        ans=[0]*n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while s:\n",
    "                ans[i]+=1\n",
    "                if heights[i]>heights[s[-1]]:\n",
    "                    s.pop()\n",
    "                else:\n",
    "                    break\n",
    "            s.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        res = [0] * len(heights)\n",
    "        stack = []\n",
    "        \n",
    "        for i in range(len(heights)-1, -1, -1): \n",
    "            cnt = 0\n",
    "            while stack and stack[-1] <= heights[i]: \n",
    "                stack.pop()\n",
    "                cnt += 1\n",
    "            res[i] = cnt if not stack else cnt + 1\n",
    "            stack.append(heights[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        stack = [inf]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            h = heights[i]\n",
    "            while stack[-1] < h:\n",
    "                stack.pop()\n",
    "                ans[i] += 1\n",
    "            if len(stack) > 1:\n",
    "                ans[i] += 1\n",
    "            stack.append(h)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(heights)\n",
    "        res = [0] * n\n",
    "        for i in range(0, n):\n",
    "            while stack and heights[stack[-1]] < heights[i]:\n",
    "                if len(stack) >= 2:\n",
    "                    res[stack[-2]] += 1\n",
    "                res[stack[-1]] += 1\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        while stack:\n",
    "            stack.pop()\n",
    "            if stack:\n",
    "                res[stack[-1]] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        stack = []  # monotonic descending stack, element: index of people \n",
    "        for i in range(n):\n",
    "            # rth people is taller than lth people\n",
    "            while stack and heights[i] >= heights[stack[-1]]:\n",
    "                ans[stack.pop()] += 1\n",
    "            if stack:\n",
    "                ans[stack[-1]] += 1\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "单调递减栈\n",
    "1.如果右边的数比栈顶的数大或者相等，那栈顶的数就不可能取到更右边的数了，所以栈顶元素被弹出。\n",
    "\n",
    "如果当前元素比栈顶大或者等于，则弹出栈顶元素。并且栈顶元素计数+1\n",
    "并且要记录当前元素是否弹出过和其一样大的元素。在入栈的时候如果其没有弹出过和其一样大的元素，则栈顶元素+1， 否则不处理。\n",
    "\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        st = []\n",
    "        cnt = [0] * n\n",
    "        for i in range(n):\n",
    "            same = False\n",
    "            while st and heights[i] >= heights[st[-1]]:\n",
    "                cnt[st[-1]] += 1\n",
    "                if heights[i] == heights[st[-1]]:\n",
    "                    same = True\n",
    "                st.pop()\n",
    "            if st and not same:\n",
    "                cnt[st[-1]] += 1\n",
    "            st.append(i)\n",
    "            \n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "单调递减栈\n",
    "1.如果右边的数比栈顶的数大或者相等，那栈顶的数就不可能取到更右边的数了，所以栈顶元素被弹出。\n",
    "\n",
    "如果当前元素比栈顶大或者等于，则弹出栈顶元素。并且栈顶元素计数+1\n",
    "并且要记录当前元素是否弹出过和其一样大的元素。在入栈的时候如果其没有弹出过和其一样大的元素，则栈顶元素+1， 否则不处理。\n",
    "\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        st = []\n",
    "        cnt = [0] * n\n",
    "        for i in range(n):\n",
    "            same = False\n",
    "            while st and heights[i] >= heights[st[-1]]:\n",
    "                cnt[st[-1]] += 1\n",
    "                if heights[i] == heights[st[-1]]:\n",
    "                    same = True\n",
    "                st.pop()\n",
    "            if st and not same:\n",
    "                cnt[st[-1]] += 1\n",
    "            st.append(i)\n",
    "            \n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        s = list()\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while s:\n",
    "                ans[i] += 1\n",
    "                if heights[i] > heights[s[-1]]:\n",
    "                    s.pop()\n",
    "                else:\n",
    "                    break\n",
    "            s.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        s = list()\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while s:\n",
    "                ans[i] += 1\n",
    "                if heights[i] > heights[s[-1]]:\n",
    "                    s.pop()\n",
    "                else:\n",
    "                    break\n",
    "            s.append(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        s = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while s:\n",
    "                ans[i] += 1\n",
    "                if heights[i] > heights[s[-1]]:\n",
    "                    s.pop()\n",
    "                else:\n",
    "                    break\n",
    "            s.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "\n",
    "    \n",
    "        res = [0] * n\n",
    "        stack= []\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack:\n",
    "                res[i] += 1\n",
    "                if heights[i] >= heights[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    break\n",
    "                    \n",
    "  \n",
    "\n",
    "            stack.append(i)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        stk = []\n",
    "        n = len(heights)\n",
    "        ans = [0]*n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stk:\n",
    "                ans[i] += 1\n",
    "                if heights[stk[-1]] < heights[i]:\n",
    "                    stk.pop()\n",
    "                else:\n",
    "                    break\n",
    "            stk.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        Q = collections.deque()\n",
    "        res = [0 for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while Q and heights[i] > Q[0]:\n",
    "                Q.popleft()\n",
    "                res[i] += 1\n",
    "            if Q:\n",
    "                res[i] += 1\n",
    "            Q.appendleft(heights[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0]*n\n",
    "        stk = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stk and heights[stk[-1]] < heights[i]:\n",
    "                ans[i] += 1\n",
    "                stk.pop()\n",
    "            if len(stk): ans[i] += 1\n",
    "            stk.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        stack = [heights[-1]]\n",
    "        ans = [0] * len(heights)\n",
    "        for i in range(len(heights)-2, -1, -1):\n",
    "            n = len(stack)\n",
    "            while stack and stack[-1] < heights[i]:\n",
    "                stack.pop()\n",
    "            ans[i] = n - max(1, len(stack)) + 1\n",
    "            stack.append(heights[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\r\n",
    "        n = len(heights)\r\n",
    "        res = [0] * n\r\n",
    "        st: list[int] = list()\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            while st and st[-1] < heights[i]:\r\n",
    "                res[i] += 1\r\n",
    "                st.pop()\r\n",
    "            if st: res[i] += 1\r\n",
    "            st.append(heights[i])\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans, q = [0 for _ in range(n)], []\n",
    "        l = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while len(q) > 0 and q[-1] <= heights[i]:\n",
    "                ans[i] += q[-1] < heights[i]\n",
    "                q.pop()\n",
    "            if len(q): ans[i] += 1 \n",
    "            q.append(heights[i])\n",
    "            l += 1   \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        s = list()\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while s:\n",
    "                ans[i] += 1\n",
    "                if heights[i] > heights[s[-1]]:\n",
    "                    s.pop()\n",
    "                else:\n",
    "                    break\n",
    "            s.append(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        res = [0] * n\n",
    "        # int[] 记录 {身高，小于等于该身高的人数} 二元组\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # 记录右侧比自己矮的人\n",
    "            count = 0\n",
    "            # 单调栈模板，计算下一个更大或相等元素（身高）\n",
    "            while stk and heights[i] > stk[-1]:\n",
    "                stk.pop()\n",
    "                count += 1\n",
    "            # 不仅可以看到比自己矮的人，如果后面存在更高的的人，也可以看到这个高人\n",
    "            res[i] = count + (not not stk)\n",
    "            stk.append(heights[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        q = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            h = heights[i]\n",
    "            cnt = 0\n",
    "            while q and q[-1] < h:\n",
    "                cnt += 1\n",
    "                q.pop()\n",
    "            ans[i] = cnt + 1 if q else cnt\n",
    "            q.append(h)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        st = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st and heights[i] >= heights[st[-1]]:\n",
    "                ans[i] += 1\n",
    "                st.pop()\n",
    "            if st:\n",
    "                ans[i] += 1\n",
    "            st.append(i)\n",
    "        return ans\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        def lt1944(nums):\n",
    "            n=len(nums)\n",
    "            res=[1 for i in range(n)]\n",
    "            l=[]\n",
    "            i=n-1\n",
    "            while i!=-1:\n",
    "                while l!=[] and nums[i]>=nums[l[-1]]:\n",
    "                    if len(l)==1:res[l[-1]]-=1\n",
    "                    res[i]+=1\n",
    "                    l.pop()\n",
    "                l.append(i)\n",
    "                i-=1\n",
    "            res[l[0]]-=1 \n",
    "            return res\n",
    "        return lt1944(heights)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        res = [0] * n\n",
    "        # int[] 记录 {身高，小于等于该身高的人数} 二元组\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # 记录右侧比自己矮的人\n",
    "            count = 0\n",
    "            # 单调栈模板，计算下一个更大或相等元素（身高）\n",
    "            while stk and heights[i] > stk[-1]:\n",
    "                stk.pop()\n",
    "                count += 1\n",
    "            # 不仅可以看到比自己矮的人，如果后面存在更高的的人，也可以看到这个高人\n",
    "            res[i] = count + (not not stk)\n",
    "            stk.append(heights[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        stack = [heights[-1]]\n",
    "        ans = [0] * len(heights)\n",
    "        for i in range(len(heights)-2, -1, -1):\n",
    "            n = len(stack)\n",
    "            while stack and stack[-1] < heights[i]:\n",
    "                stack.pop()\n",
    "            ans[i] = n - max(1, len(stack)) + 1\n",
    "            stack.append(heights[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "\n",
    "        res = [0] * n\n",
    "        s = []\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            count = 0\n",
    "            while s and s[-1] <= heights[i]:\n",
    "                count += 1\n",
    "                s.pop()\n",
    "            \n",
    "            res[i] = count + 1 if s else count\n",
    "            s.append(heights[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        stk = []\n",
    "        res = [0] * n\n",
    "        for i in range(n - 1,-1,-1) :\n",
    "            h = heights[i]\n",
    "            cnt = 0\n",
    "            while stk and stk[-1] < h :\n",
    "                stk.pop()\n",
    "                cnt += 1\n",
    "            if stk and stk[-1] == h :\n",
    "                stk.pop()\n",
    "                cnt += 1\n",
    "            if stk :\n",
    "                cnt += 1\n",
    "            stk.append(h)\n",
    "            res[i] = cnt\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(heights)\n",
    "        # 单调减栈\n",
    "        st = []\n",
    "        ans = [0] * n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            h = heights[i]\n",
    "            while st and heights[st[-1]] < h:\n",
    "                st.pop()\n",
    "                ans[i]+=1\n",
    "            if st:\n",
    "                ans[i]+=1\n",
    "            st.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(heights)\n",
    "        res = [0] * n\n",
    "\n",
    "        s = []\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while s:\n",
    "                res[i] += 1\n",
    "\n",
    "                if heights[i] > heights[s[-1]]:\n",
    "                    s.pop()\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            s.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and stk[-1] < heights[i]:\n",
    "                ans[i] += 1\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                ans[i] += 1\n",
    "            stk.append(heights[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        stack, n = [], len(heights)\n",
    "        ans = [0] * n #最右边谁也看不到为0，所以初始化都是0\n",
    "        for i in range(n - 1, -1, -1):#逆序range(2,-1,-1)右开区间相当于倒数第一到零\n",
    "            while stack and heights[i] > heights[stack[-1]]:\n",
    "                    ans[i] += 1\n",
    "                    stack.pop()\n",
    "            if stack:\n",
    "                ans[i] += 1 \n",
    "            stack.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk:\n",
    "                ans[i] += 1\n",
    "                if heights[i] <= heights[stk[-1]]:\n",
    "                    break\n",
    "                stk.pop()\n",
    "            stk.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "\n",
    "\n",
    "        n = len(heights)\n",
    "        res = [0] * n\n",
    "\n",
    "        s = []\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while s:\n",
    "\n",
    "                res[i] += 1\n",
    "\n",
    "                if heights[i] > heights[s[-1]]:\n",
    "                    s.pop()\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            s.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        stack = []  # monotonic descending stack, element: index of people \n",
    "        for i in reversed(range(n)):\n",
    "            # rth people is taller than lth people\n",
    "            while stack and heights[i] > heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "                ans[i] += 1\n",
    "            if stack:\n",
    "                ans[i] += 1\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        # 找到每个数右边最大的那个点\n",
    "        n = len(heights)\n",
    "        st = []\n",
    "        ans = [0] * n\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cnt = 0\n",
    "            while st and heights[i] > heights[st[-1]]:\n",
    "                st.pop()\n",
    "                cnt += 1\n",
    "            if st:\n",
    "                cnt += 1\n",
    "            ans[i] = cnt\n",
    "            st.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        res = [0] * n\n",
    "        # int[] 记录 {身高，小于等于该身高的人数} 二元组\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # 记录右侧比自己矮的人\n",
    "            count = 0\n",
    "            # 单调栈模板，计算下一个更大或相等元素（身高）\n",
    "            while stk and heights[i] > stk[-1]:\n",
    "                stk.pop()\n",
    "                count += 1\n",
    "            # 不仅可以看到比自己矮的人，如果后面存在更高的的人，也可以看到这个高人\n",
    "            # res[i] = count + (not not stk)\n",
    "            res[i] = count + 1 if len(stk) > 0 else count\n",
    "            stk.append(heights[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans, q = [0 for _ in range(n)], [0 for _ in range(n)]\n",
    "        l = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while l > 0 and q[l - 1] <= heights[i]:\n",
    "                ans[i] += q[l - 1] < heights[i]\n",
    "                l -= 1\n",
    "            if l > 0: ans[i] += 1 \n",
    "            q[l] = heights[i]\n",
    "            l += 1   \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        dq = deque()\n",
    "        res = []\n",
    "        for i in range(len(heights) - 1, -1, -1):\n",
    "            cnt = 0\n",
    "            while dq and dq[-1] < heights[i]: \n",
    "                dq.pop()\n",
    "                cnt += 1\n",
    "            res.append(cnt + (1 if dq else 0))\n",
    "            dq.append(heights[i])\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        # i 是不是可以看到j的条件\n",
    "        # 1 j在i的右边\n",
    "        # 2 heights[j] <= heights[i]\n",
    "        # 3 j 也可以看见i（向左）\n",
    "\n",
    "        n = len(heights)\n",
    "        # 1234 r2l\n",
    "        stack = []\n",
    "        ans = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            # 首先要和栈中元素做比较\n",
    "            if not stack:\n",
    "                ans.append(0)\n",
    "            elif stack:\n",
    "                # 如果右侧元素平等或更高\n",
    "                if heights[i] <= heights[stack[-1]]:\n",
    "                    ans.append(1)\n",
    "                # 如果当前的元素比右边的元素更大\n",
    "                else:\n",
    "                    tempStack = stack.copy()\n",
    "                    cnt = 0\n",
    "                    while tempStack and heights[i] >= heights[tempStack[-1]]:\n",
    "                        tempStack.pop()\n",
    "                        cnt += 1\n",
    "                    # 3 1 2 4, 也就是右边的一个高个子\n",
    "                    if tempStack and heights[i] < heights[tempStack[-1]]:\n",
    "                        cnt += 1\n",
    "                    ans.append(cnt)\n",
    "            # 然后是入栈流程（朴素单调栈）\n",
    "            # 从顶到底的单调递增栈，1234 l2r\n",
    "            # 小于栈顶元素可以直接入栈\n",
    "            while stack and heights[i] >= heights[stack[-1]]:\n",
    "                # 更高的元素会让右边的元素全部都看不见\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        ans.reverse()\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [0] * n\n",
    "        stack = []\n",
    "        heights = heights[::-1]\n",
    "        for i , h in enumerate(heights):\n",
    "            t = 0\n",
    "            while stack and heights[stack[-1]] < h:\n",
    "                stack.pop()\n",
    "                t += 1\n",
    "            if stack:\n",
    "                ans[n-i-1] = t + 1\n",
    "            else:\n",
    "                ans[n-i-1] = t\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        from collections import deque\n",
    "        myStack = deque()\n",
    "        res = [1] * len(heights)\n",
    "        res[-1] = 0\n",
    "        for idx, height in enumerate(heights):\n",
    "            while myStack and height > myStack[-1][1]:\n",
    "                curidx, curheight = myStack.pop()\n",
    "                if myStack:\n",
    "                    res[myStack[-1][0]] += 1\n",
    "            myStack.append((idx, height))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        answer = [0] * n\n",
    "        stack = []  # 存储（身高，索引）\n",
    "\n",
    "        for i, h in enumerate(heights):\n",
    "            while stack and stack[-1][0] <= h:\n",
    "                _, idx = stack.pop()\n",
    "                answer[idx] += 1\n",
    "            if stack:\n",
    "                answer[stack[-1][1]] += 1\n",
    "            stack.append((h, i))\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canSeePersonsCount(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        stack = []\n",
    "        res = [0] * n\n",
    "        for i, h in enumerate(heights):\n",
    "            while stack and stack[-1][0] < h:\n",
    "                hei, child = stack.pop()\n",
    "                res[child] += 1\n",
    "            if stack:\n",
    "                res[stack[-1][-1]] += 1\n",
    "            stack.append((h, i))\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
